/**
 * 
 */
package sorting;

import linkedlist.Node;
import utils.CreateUtils;
import utils.PrintUtils;

/**
 * @author Michael
 * 
 */
public class MergeSort
{

    public static int[] mergeSort(int[] arr, int start, int end)
    {
        if (arr == null || arr.length == 0 || end >= arr.length || start > end || start < 0 || end < 0)
            return arr;

        if (start < end)
        {
            int mid = start + (end - start) / 2;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid + 1, end);
            merge(arr, start, end);
        }

        return arr;
    }

    private static void merge(int[] arr, int start, int end)
    {
        if (arr == null || arr.length == 0 || end >= arr.length || start > end || start < 0 || end < 0)
            return;

        int mid = start + (end - start) / 2;
        int[] tmpArr = new int[end - start + 1];
        int p1 = start, p2 = mid + 1, tmp = 0;
        while (p1 <= mid && p2 <= end)
        {
            if (arr[p1] <= arr[p2])
            {
                tmpArr[tmp++] = arr[p1++];
            }
            else
            {
                tmpArr[tmp++] = arr[p2++];
            }
        }
        if (p2 > end)
        {
            while (p1 <= mid)
            {
                tmpArr[tmp++] = arr[p1++];
            }
        }
        else
        {
            end = p2 - 1;
        }
        for (p1 = start, tmp = 0; p1 <= end; p1++, tmp++)
        {
            arr[p1] = tmpArr[tmp];
        }
    }

    private static Node<Integer> merge2Sorted(Node<Integer> node1, Node<Integer> node2)
    {
        // TODO
        return null;
    }

    /**
	 * 
	 */
    public MergeSort()
    {
        // TODO Auto-generated constructor stub
    }

    /**
     * @param args
     */
    public static void main(String[] args)
    {

        int[] a = CreateUtils.randNonNegIntArray(50, 50);
        PrintUtils.printArray(a);
        PrintUtils.printArray(mergeSort(a, 0, a.length - 1));

        // int[] arr = { 3, 6, 1, 5, 2, 8 };
        // PrintUtils.printArray(arr);
        // System.out
        // .println("inversions:" + mergeSort(arr, 0, arr.length - 1, 0));
        // PrintUtils.printArray(arr);
        //
        // arr = new int[] { 9, 1, 0, 5, 4 };
        // PrintUtils.printArray(arr);
        // System.out
        // .println("inversions:" + mergeSort(arr, 0, arr.length - 1, 0));
        // PrintUtils.printArray(arr);
        //
        // arr = new int[] { 9, 8, 7, 6, 5, 4, 3, 1, 2 };
        // PrintUtils.printArray(arr);
        // System.out
        // .println("inversions:" + mergeSort(arr, 0, arr.length - 1, 0));
        // PrintUtils.printArray(arr);

    }

}
